{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 协同过滤推荐\n",
    "\n",
    "\"\"\"\n",
    "    W = N(x) 交集 N(y) / N(x) 并集 N(y)\n",
    "\n",
    "        用户\t喜爱的物品\n",
    "        A\t{a,b,d}\n",
    "        B\t{a,c,d}\n",
    "        C\t{b,e}\n",
    "        D\t{c,d,e}\n",
    "    分母：\n",
    "        a\t{A,B}\n",
    "        b\t{A,C}\n",
    "        c\t{B,D}\n",
    "        d\t{A,B,D}\n",
    "        e\t{C,D}\n",
    "\n",
    "    分子： \n",
    "            A\tB\tC\tD\n",
    "        A\t0\t2\t1\t1\n",
    "        B\t2\t0\t0\t2\n",
    "        C\t1\t0\t0\t1\n",
    "        D\t1\t2\t1\t0\n",
    "    \n",
    "--> 相似度矩阵\n",
    "    \n",
    "        A\t    B\t    C\t    D\n",
    "    A\t0\t    0.67\t0.41\t0.33\n",
    "    B\t0.67\t0\t0\t0.67\n",
    "    C\t0.41\t0\t0\t0.41\n",
    "    D\t0.33\t0.67\t0.41\t0\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'Utils'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mModuleNotFoundError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[1;32mc:\\Users\\17914\\Desktop\\travelCF\\base\\utils\\cf_recommend.ipynb 单元格 2\u001b[0m line \u001b[0;36m4\n\u001b[0;32m      <a href='vscode-notebook-cell:/c%3A/Users/17914/Desktop/travelCF/base/utils/cf_recommend.ipynb#W1sZmlsZQ%3D%3D?line=1'>2</a>\u001b[0m \u001b[39mimport\u001b[39;00m \u001b[39mrandom\u001b[39;00m\n\u001b[0;32m      <a href='vscode-notebook-cell:/c%3A/Users/17914/Desktop/travelCF/base/utils/cf_recommend.ipynb#W1sZmlsZQ%3D%3D?line=2'>3</a>\u001b[0m \u001b[39mimport\u001b[39;00m \u001b[39mpandas\u001b[39;00m \u001b[39mas\u001b[39;00m \u001b[39mpd\u001b[39;00m\n\u001b[1;32m----> <a href='vscode-notebook-cell:/c%3A/Users/17914/Desktop/travelCF/base/utils/cf_recommend.ipynb#W1sZmlsZQ%3D%3D?line=3'>4</a>\u001b[0m \u001b[39mfrom\u001b[39;00m \u001b[39mUtils\u001b[39;00m \u001b[39mimport\u001b[39;00m modelsave\n\u001b[0;32m      <a href='vscode-notebook-cell:/c%3A/Users/17914/Desktop/travelCF/base/utils/cf_recommend.ipynb#W1sZmlsZQ%3D%3D?line=4'>5</a>\u001b[0m \u001b[39mfrom\u001b[39;00m \u001b[39mcollections\u001b[39;00m \u001b[39mimport\u001b[39;00m defaultdict\n\u001b[0;32m      <a href='vscode-notebook-cell:/c%3A/Users/17914/Desktop/travelCF/base/utils/cf_recommend.ipynb#W1sZmlsZQ%3D%3D?line=5'>6</a>\u001b[0m \u001b[39mfrom\u001b[39;00m \u001b[39moperator\u001b[39;00m \u001b[39mimport\u001b[39;00m itemgetter\n",
      "\u001b[1;31mModuleNotFoundError\u001b[0m: No module named 'Utils'"
     ]
    }
   ],
   "source": [
    "\n",
    "import math\n",
    "import random\n",
    "import pandas as pd\n",
    "from Utils import modelsave\n",
    "from collections import defaultdict\n",
    "from operator import itemgetter\n",
    "\n",
    "def LoadMovieLensData(filepath, train_rate):\n",
    "    ratings = pd.read_table(filepath, sep=\"::\", header=None, names=[\"UserID\", \"MovieID\", \"Rating\", \"TimeStamp\"],\\\n",
    "                            engine='python')\n",
    "    ratings = ratings[['UserID','MovieID']]\n",
    "\n",
    "    train = []\n",
    "    test = []\n",
    "    random.seed(3)\n",
    "    for idx, row in ratings.iterrows():\n",
    "        user = int(row['UserID'])\n",
    "        item = int(row['MovieID'])\n",
    "        if random.random() < train_rate:\n",
    "            train.append([user, item])\n",
    "        else:\n",
    "            test.append([user, item])\n",
    "    return PreProcessData(train), PreProcessData(test)\n",
    "\n",
    "def PreProcessData(originData):\n",
    "    \"\"\"\n",
    "    建立User-Item表，结构如下：\n",
    "        {\"User1\": {MovieID1, MoveID2, MoveID3,...}\n",
    "         \"User2\": {MovieID12, MoveID5, MoveID8,...}\n",
    "         ...\n",
    "        }\n",
    "    \"\"\"\n",
    "    trainData = dict()\n",
    "    for user, item in originData:\n",
    "        trainData.setdefault(user, set())\n",
    "        trainData[user].add(item)\n",
    "    return trainData\n",
    "\n",
    "class UserCF(object):\n",
    "    \"\"\" User based Collaborative Filtering Algorithm Implementation\"\"\"\n",
    "    def __init__(self, trainData, similarity=\"cosine\"):\n",
    "        self._trainData = trainData\n",
    "        self._similarity = similarity\n",
    "        self._userSimMatrix = dict() # 用户相似度矩阵\n",
    "\n",
    "    def similarity(self):\n",
    "        # 建立User-Item倒排表\n",
    "        item_user = dict()\n",
    "        for user, items in self._trainData.items():\n",
    "            for item in items:\n",
    "                item_user.setdefault(item, set())\n",
    "                item_user[item].add(user)\n",
    "\n",
    "        # 建立用户物品交集矩阵W, 其中C[u][v]代表的含义是用户u和用户v之间共同喜欢的物品数\n",
    "        for item, users in item_user.items():\n",
    "            for u in users:\n",
    "                for v in users:\n",
    "                    if u == v:\n",
    "                        continue\n",
    "                    self._userSimMatrix.setdefault(u, defaultdict(int))\n",
    "                    if self._similarity == \"cosine\":\n",
    "                        self._userSimMatrix[u][v] += 1 #将用户u和用户v共同喜欢的物品数量加一\n",
    "                    elif self._similarity == \"iif\":\n",
    "                        self._userSimMatrix[u][v] += 1. / math.log(1 + len(users))\n",
    "\n",
    "        # 建立用户相似度矩阵\n",
    "        for u, related_user in self._userSimMatrix.items():\n",
    "            # 相似度公式为 |N[u]∩N[v]|/sqrt(N[u]||N[v])\n",
    "            for v, cuv in related_user.items():\n",
    "                nu = len(self._trainData[u])\n",
    "                nv = len(self._trainData[v])\n",
    "                self._userSimMatrix[u][v] = cuv / math.sqrt(nu * nv)\n",
    "\n",
    "    def recommend(self, user, N, K):\n",
    "        \"\"\"\n",
    "        用户u对物品i的感兴趣程度：\n",
    "            p(u,i) = ∑WuvRvi\n",
    "            其中Wuv代表的是u和v之间的相似度， Rvi代表的是用户v对物品i的感兴趣程度，因为采用单一行为的隐反馈数据，所以Rvi=1。\n",
    "            所以这个表达式的含义是，要计算用户u对物品i的感兴趣程度，则要找到与用户u最相似的K个用户，对于这k个用户喜欢的物品且用户u\n",
    "            没有反馈的物品，都累加用户u与用户v之间的相似度。\n",
    "        :param user: 被推荐的用户user\n",
    "        :param N: 推荐的商品个数\n",
    "        :param K: 查找的最相似的用户个数\n",
    "        :return: 按照user对推荐物品的感兴趣程度排序的N个商品\n",
    "        \"\"\"\n",
    "        recommends = dict()\n",
    "        # 先获取user具有正反馈的item数组\n",
    "        related_items = self._trainData[user]\n",
    "        # 将其他用户与user按照相似度逆序排序之后取前K个\n",
    "        for v, sim in sorted(self._userSimMatrix[user].items(), key=itemgetter(1), reverse=True)[:K]:\n",
    "            # 从与user相似的用户的喜爱列表中寻找可能的物品进行推荐\n",
    "            for item in self._trainData[v]:\n",
    "                # 如果与user相似的用户喜爱的物品与user喜欢的物品重复了，直接跳过\n",
    "                if item in related_items:\n",
    "                    continue\n",
    "                recommends.setdefault(item, 0.)\n",
    "                recommends[item] += sim\n",
    "        # 根据被推荐物品的相似度逆序排列，然后推荐前N个物品给到用户\n",
    "        return dict(sorted(recommends.items(), key=itemgetter(1), reverse=True)[:N])\n",
    "\n",
    "    def train(self):\n",
    "        self.similarity()\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    train, test = LoadMovieLensData(\"../Data/ml-1m/ratings.dat\", 0.8)\n",
    "    print(\"train data size: %d, test data size: %d\" % (len(train), len(test)))\n",
    "    UserCF = UserCF(train)\n",
    "    UserCF.train()\n",
    "\n",
    "    # 分别对测试集中的前4个用户进行电影推荐\n",
    "    print(UserCF.recommend(list(test.keys())[0], 5, 80))\n",
    "    print(UserCF.recommend(list(test.keys())[1], 5, 80))\n",
    "    print(UserCF.recommend(list(test.keys())[2], 5, 80))\n",
    "    print(UserCF.recommend(list(test.keys())[3], 5, 80))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
